#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int findNum(int num, vector<int>& nums) {
    while (num>=-1) {
        if (nums[num] > 0) {
            nums[num]--;
            return num;
        }
        num++;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        vector<int> num(10);
        vector<int> ans(11);
        for (int i = 0; i < 10; i++) {
            num[s[i] - '0']++;
        }
        for (int i = 1; i < 11; i++) {
            int x=findNum(10 - i, num);
            ans[i] = x;
        }
        for (int i = 1; i < 11; i++) {
            cout << ans[i];
            if (i == 10) {
                cout << endl;
            }
        }
    }
    return 0;
}